class Node:
    def __init__(self, data, parent):
        self.data=data
        self.parent=parent

class UnionFindSet:
    def __init__(self,elements):
        self.elements=sorted(set(elements))
        self.nodes=[ Node(data=element,parent=None)
                     for element in self.elements ]
        self.subsets=len(elements)
    def node(self,element):
        return self.nodes[self.elements.index(element)]
    def find(self,element):
        root=self.node(element)
        while root.parent != None:
            root=root.parent
        return root.data
    def union(self,element1,element2):
        root1=self.node(element1)
        root2=self.node(element2)
        while root1.parent != None:
            root1=root1.parent
        while root2.parent != None:
            root2=root2.parent
        if root1.data < root2.data:
            root2.parent=root1
        else:
            root1.parent=root2
        self.subsets-=1
    def is_same_set(self,element1,element2):
        return self.find(element1) == self.find(element2)

def kruskal(graph):
    vertexes=UnionFindSet(graph[0])
    edges=sorted(graph[1],key=lambda x: x[-1])
    result=[]
    while vertexes.subsets > 1:
        edge=edges.pop(0)
        vertex1,vertex2=edge[0],edge[1]
        if vertexes.is_same_set(vertex1,vertex2):
            continue
        else:
            result.append(edge)
            vertexes.union(vertex1,vertex2)
    return result

vertexes=['A','B','C','D','S','T']
edges=[
    ('A','B',6),('A','C',3),('A','S',7),
    ('B','C',4),('B','D',2),('B','T',5),
    ('C','D',3),('C','S',8),('D','T',2)
]
graph=(vertexes,edges)
print(kruskal(graph))
